/**
 * 75. 颜色分类
 * https://leetcode.cn/problems/sort-colors/description/
 */

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int left = -1, right = n, i = 0;
        while(i < right) {
             if(nums[i] == 0) swap(nums, ++left, i++);
             else if(nums[i] == 1) i++;
             else swap(nums, --right, i);//nums[i] == 2
        }
    }
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}